package LeetCode_692;
import java.util.*;
/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/13 17:14
 * 优先队列解决
 *
 */
class Solution2 {
    static class Cmp implements Comparator<Map.Entry<String, Integer>> {
        // leetcode-1 < coding-1 < love-2 < i-2
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            String word1 = o1.getKey();
            int count1 = o1.getValue();
            String word2 = o2.getKey();
            int count2 = o2.getValue();

            if (count1 < count2) {
                // o1: leetcode-1
                // o2: i-2
                // o1 < o2
                return -1;
            } else if (count1 > count2) {
                return 1;
            }

            return word2.compareTo(word1);
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> countMap = new TreeMap<>();
        for (String w : words) {
            int count = countMap.getOrDefault(w, 0);
            countMap.put(w, count + 1);
        }

        // 得到每个单词的出现次数

        // 使用优先级队列完成
        // 优先级队列中的元素类型也使用 Map.Entry<单词, 次数>
        // 优先级队列是小堆，越小的越在堆顶
        // 堆顶元素是相比较容易被淘汰的元素
        // i-2 和 love-2 相比较，love-2 先于 i-2 被淘汰，所以 love-2 < i2
        // love-2 和 leetcode-1 相比较，leetcode-1 先于 love-2 被淘汰，所以 leetcode-1 < love2
        // 所以，最终顺序
        // leetcode-1 < coding-1 < love-2 < i-2
        Cmp comparator = new Cmp();

        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>(comparator);

        Set<Map.Entry<String, Integer>> entrySet = countMap.entrySet();

        // 先遍历 entrySet，把 前 k 个放入优先级队列
        // 之后的，再去和堆顶进行比较
        int n = 0;
        for (Map.Entry<String, Integer> entry : entrySet) {
            if (n < k) {
                // 说明是 前 k 个
                queue.offer(entry);
            } else {
                // 后边的
                // 比较 entry 和 queue.peek()
                // entry: c-3
                // queue.peek(): love-1
                // 要被淘汰
                // leetcode-1 < coding-1 < love-2 < i-2 < c-3
                // entry > queue.peek()
                // int cmp = comparator.compare(entry, queue.peek())
                // cmp > 0
                int cmp = comparator.compare(entry, queue.peek());
                if (cmp > 0) {
                    queue.poll();
                    queue.offer(entry);
                }
            }
            n++;
        }

        // 目前优先级队列中维护的就是 k 个候选人
        // 假如 k = 2
        // 堆顶 love-2     i-2 堆底
        // 不断调用 queue.poll() 的顺序将是
        // love-2 i-2
        // 但我们需要的结果是 i-2 love-2
        // 所以使用头插的方式插入到结果 List 中
        // 因为使用头插，就使用 LinkedList，而不是 ArrayList 了
        List<String> ans = new LinkedList<>();
        while(!queue.isEmpty()){
            Map.Entry<String, Integer> entry = queue.poll();
            String word = entry.getKey();
            ans.add(0,word);
        }

        return ans;
    }
}
